package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/insertion-sort-list/'>对链表进行插入排序(Insertion Sort List)</a>
 * <p>给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
 * <p>
 *  插入排序 算法的步骤:
 *  <ol>
 *     <li>插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。</li>
 *     <li>每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。</li>
 *     <li>重复直到所有输入数据插入完为止。</li>
 *  </ol>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入: head = [4,2,1,3]
 *      输出: [1,2,3,4]
 *
 * 示例 2：
 *      输入: head = [-1,5,3,4,0]
 *      输出: [-1,0,3,4,5]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>列表中的节点数在 [1, 5000]范围内</li>
 *      <li>-5000 <= Node.val <= 5000</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/4 15:37
 */
public class LC0147InsertionSortList_M {

    static class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head);
            // 已经有序的节点
            ListNode sortedNode = dummyHead;
            // 待排节点
            ListNode currNode = head;
            while (currNode != null) {
                if (sortedNode.val <= currNode.val) {
                    sortedNode = currNode;

                } else {
                    // 从头结点开始寻找到合适的位置
                    ListNode tempNode = dummyHead;
                    while (tempNode.next.val <= currNode.val) {
                        tempNode = tempNode.next;
                    }
                    // 将currNode 插入到 tempNode 的后面
                    ListNode nextNode = currNode.next;
                    currNode.next = tempNode.next;
                    tempNode.next = currNode;
                    sortedNode.next = nextNode;
                }
                currNode = sortedNode.next;
            }
            return dummyHead.next;
        }
    }






    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head);
        ListNode prev = dummyHead;
        ListNode curr = head;
        while (curr != null ) {
            if (prev.val <= curr.val) {
                prev = curr;
                curr = curr.next;
            } else {
                // 从头节点出发，找到第一个不满足的节点
                ListNode tempNode = dummyHead;
                while (tempNode.next.val <= curr.val) {
                    tempNode = tempNode.next;
                }
                // 插入
                ListNode nextNode = curr.next;
                curr.next = tempNode.next;
                tempNode.next = nextNode;
                curr = nextNode;
            }
        }
        return dummyHead.next;
    }
}
